package problems.daily.y2021m7;

import java.util.Iterator;
import java.util.Map;
import java.util.Stack;
import java.util.TreeMap;

/**
 * @author habitplus
 * @since 2021-07-05 10:02
 */
public class T20210705N1 {
    // 726. 原子的数量
    // 给定一个化学式 formula（作为字符串），返回每种原子的数量。
    // 原子总是以一个大写字母开始，接着跟随 0个或任意个小写字母，表示原子的名字。
    // 如果数量大于 1，原子后会跟着数字表示原子的数量。如果数量等于 1 则不会跟数字。例如，H2O 和 H2O2 是可行的，但 H1O2 这个表达是不可行的。
    // 两个化学式连在一起是新的化学式。例如 H2O2He3Mg4 也是化学式。
    // 一个括号中的化学式和数字（可选择性添加）也是化学式。例如 (H2O2) 和 (H2O2)3 是化学式。
    // 给定一个化学式，输出所有原子的数量。格式为：第一个（按字典序）原子的名子，跟着它的数量（如果数量大于 1），然后是第二个原子的名字（按字典序），跟着它的数量（如果数量大于 1），以此类推。
    //
    // 注意:
    // 所有原子的第一个字母为大写，剩余字母都是小写。
    // formula 的长度在 [1, 1000] 之间。
    // formula 只包含字母、数字和圆括号，并且题目中给定的是合法的化学式。
    //
    // 链接：https://leetcode-cn.com/problems/number-of-atoms
    public String countOfAtoms(String formula) {
        if (formula == null || "".equals(formula)) {
            return "";
        }

        // 用栈来保存括号里面的化学元素
        Stack<Atom> stack = new Stack<>();
        // 临时栈
        Stack<Atom> tmpStack = new Stack<>();
        // 存储每个化学原子的数量
        TreeMap<String, Integer> treeMap = new TreeMap<>();

        char[] chs = formula.toCharArray();
        int len = chs.length;
        String k;
        int num, cnt, j, i = 0;
        // 记录括号的数量
        int bracketNo = 0;
        while (i < len) {
            if (chs[i] == '(') {
                bracketNo++;
                i++;
            } else if (chs[i] == ')') {
                // 读取后面的数字
                i++;
                num = 0;
                while (i < len && Character.isDigit(chs[i])) {
                    num = num * 10 + (chs[i] - '0');
                    i++;
                }
                num = num == 0 ? 1 : num;

                // 具有相同左括号编号的元素出栈
                while (!stack.isEmpty() && stack.peek().bracketNo == bracketNo) {
                    Atom o = stack.pop();
                    if (o.bracketNo > 1) {
                        // 结果继续进栈
                        o.bracketNo--;
                        o.cnt = o.cnt * num;
                        tmpStack.push(o);
                    } else {
                        cnt = treeMap.getOrDefault(o.name, 0);
                        treeMap.put(o.name, cnt + o.cnt * num);
                    }
                }

                // 如果有临时结果，进行进栈
                while (!tmpStack.isEmpty()) {
                    stack.push(tmpStack.pop());
                }

                bracketNo--;
            } else {
                // 提取 原子名称
                j = i++;
                while (i < len && Character.isLowerCase(chs[i])) {
                    i++;
                }
                k = formula.substring(j, i);

                // 提取 原子的数量
                num = 0;
                while (i < len && Character.isDigit(chs[i])) {
                    num = num * 10 + (chs[i] - '0');
                    i++;
                }
                num = num == 0 ? 1 : num;

                if (bracketNo > 0) {
                    stack.push(new Atom(k, num, bracketNo));
                } else {
                    // 没有左括号直接存 Map
                    cnt = treeMap.getOrDefault(k, 0);
                    treeMap.put(k, cnt + num);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        Iterator<Map.Entry<String, Integer>> iter = treeMap.entrySet().iterator();
        while (iter.hasNext()) {
            Map.Entry<String, Integer> entry = iter.next();
            k = entry.getKey();
            cnt = entry.getValue();
            if (cnt > 1) {
                sb.append(k).append(cnt);
            } else {
                sb.append(k);
            }
        }
        return sb.toString();
    }

    static class Atom {
        // 化学原子的名称
        String name;
        // 化学原子的数量
        int cnt;
        // 从左到右 左括号的编号（从 1 开始）
        int bracketNo;

        public Atom(String name, int cnt, int bracketNo){
            this.name = name;
            this.cnt = cnt;
            this.bracketNo = bracketNo;
        }
    }

    public static void main(String[] args) {
        System.out.println(new T20210705N1().countOfAtoms("H2O"));
        System.out.println(new T20210705N1().countOfAtoms("Mg(OH)2"));
        System.out.println(new T20210705N1().countOfAtoms("K4(ON(SO3)2)2"));
    }

}
